package leetcode;

import javax.swing.tree.TreeNode;

/**
 * 二叉搜索树中的插入操作
 */
public class Solution22 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            TreeNode node = new TreeNode(val);
            return node;
        }
        TreeNode newRoot = root;
        TreeNode pre = root;
        while(root != null){
            pre = root;
            if(root.val < val){
                root = root.right;
            }else if(root.val > val){
                root = root.left;
            }
        }

        if(pre.val > val){
            pre.left = new TreeNode(val);
        }else{
            pre.right = new TreeNode(val);
        }

        return newRoot;
    }
}
